import pandas as pd
import numpy as np
import matplotlib.pyplot as plt

# 读取坐标文件
coordinates_df = pd.read_excel("C:\\Users\\86191\\Desktop\\资料PPT\\大三学期\\智能优化算法\\湖大各院坐标.xlsx")
# 提取坐标
coordinates = coordinates_df[['经度', '纬度']].values

# 读取距离矩阵文件
distance_df = pd.read_excel("C:\\Users\\86191\\Desktop\\资料PPT\\大三学期\\智能优化算法\\湖大各学院距离矩阵.xls", index_col=0)
# 将距离矩阵转换为NumPy数组
dist_matrix = distance_df.values

# 粒子群优化算法
class PSO:
    def __init__(self, num_particles, num_iterations, w, c1, c2, distance_matrix):
        self.num_particles = num_particles
        self.num_iterations = num_iterations
        self.w = w  # 惯性权重
        self.c1 = c1  # 个体学习因子
        self.c2 = c2  # 社会学习因子
        self.distance_matrix = distance_matrix
        self.particles = [np.random.permutation(len(distance_matrix)) for _ in range(num_particles)]
        self.best_positions = np.copy(self.particles)
        self.best_distances = np.array([self.calculate_distance(particle) for particle in self.particles])
        self.global_best_position = self.particles[np.argmin(self.best_distances)]
        self.global_best_distance = np.min(self.best_distances)

    def calculate_distance(self, particle):
        # 计算路径的总距离
        return sum(self.distance_matrix[particle[i], particle[(i + 1) % len(particle)]] for i in range(len(particle)))

    def two_opt(self, tour):
        # 应用2-opt算法来优化路径
        best_tour = tour.copy()
        best_distance = self.calculate_distance(best_tour)
        for i in range(len(tour)):
            for j in range(i+1, len(tour)):
                if i == 0 and j == len(tour) - 1:
                    continue
                new_tour = np.copy(best_tour)
                new_tour[i:j] = new_tour[i:j][::-1]  # 反转路径段
                new_distance = self.calculate_distance(new_tour)
                if new_distance < best_distance:
                    best_tour = new_tour
                    best_distance = new_distance
        return best_tour, best_distance

    def update_velocity(self, particle, best_position, global_best_position):
        # 更新粒子的速度（在这里，速度更新是通过交换两个随机点来模拟的）
        new_particle = np.copy(particle)
        for _ in range(2):  # 每次迭代交换两个点
            i, j = np.random.randint(0, len(particle), size=2)
            new_particle[i], new_particle[j] = new_particle[j], new_particle[i]
        return new_particle

    def optimize(self):
        for _ in range(self.num_iterations):
            for i in range(self.num_particles):
                new_position = self.update_velocity(self.particles[i], self.best_positions[i], self.global_best_position)
                new_distance = self.calculate_distance(new_position)
                if new_distance < self.best_distances[i]:
                    self.best_positions[i] = new_position
                    self.best_distances[i] = new_distance
                    if new_distance < self.global_best_distance:
                        self.global_best_position = new_position
                        self.global_best_distance = new_distance
                # 应用2-opt优化
                self.best_positions[i], distance = self.two_opt(self.best_positions[i])
                if distance < self.best_distances[i]:
                    self.best_distances[i] = distance
                if distance < self.global_best_distance:
                    self.global_best_position = self.best_positions[i]
                    self.global_best_distance = distance
                self.particles[i] = self.best_positions[i]

# 设置PSO参数
num_particles = 30
num_iterations = 100
w = 0.5
c1 = 1
c2 = 1

# 创建PSO对象并优化
pso = PSO(num_particles, num_iterations, w, c1, c2, dist_matrix)
pso.optimize()

# 打印最优路径长度
print("Optimal path length:", pso.global_best_distance)

# 打印最优顺序
print("Optimal order of visiting colleges:")
for idx in pso.global_best_position:
    print(distance_df.index[idx])

# 可视化结果
def plot_tsp_route(best_path, coordinates):
    x, y = coordinates[:, 0], coordinates[:, 1]
    plt.figure(figsize=(10, 8))
    plt.plot(x[best_path], y[best_path], 'o-r')  # 绘制路径
    plt.plot(x[best_path[-1]], y[best_path[-1]], 'bo')  # 绘制起点
    plt.plot(x[best_path[0]], y[best_path[0]], 'bo')  # 绘制终点
    plt.plot(x[[best_path[-1], best_path[0]]], y[[best_path[-1], best_path[0]]], 'r-')  # 连接起点和终点
    plt.xlabel('Longitude')
    plt.ylabel('Latitude')
    plt.title('TSP Route')
    plt.show()

# 绘制最佳路径
plot_tsp_route(pso.global_best_position, coordinates)